﻿#define _CRT_SECURE_NO_WARNINGS 1
using namespace std;
#include "bitsstdC.h"
/*
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c
*/
//双指针解法
//class Solution {
//public:
//    bool judgeSquareSum(int c) {
//        int a = 0, b = (int)sqrt(c);//一开始时，我们分别将a=0,b=✓c。
//          space::O(1),因为用到额外的指针，所以空间复杂度为O(1),
//          time::O(sqrt(c))
//        while (a <= b) {
//            //为了避免整型溢出，溢出后会导致负数.
//            //于是由a² + b² = c推导成a²=c-b²或者b²=c-a²;
//            //那判断条件我们写成a*a<c-b*b或者b*b<c-a*a,从而有效地避免溢出
//            if (b * b == c - a * a) {
//                return true;
//            }
//            else if (b * b < c - a * a) {
//                ++a;//当b²<c-a²，说明当前的值是小于目标值的，因此让左指针a++，
//            }
//            else {
//                --b;//当b²＞c-a²，说明当前的值是大于目标值的，因此让右指针b--
//            }
//        }
//        return false;
//    }
//};
//
//
// 

//class Solution {
//public:
//    bool judgeSquareSum(int c) {
//        //为什么只枚举到c的一半？这是因为我们可以把c/2的值当作一面镜子，然后两边的值互相反射，因此我们只要发现某个数字重新出现的话，我们就可以停止枚举了
//        for (int a = 0; a * a <= c / 2; ++a) {
//            //space::O(1)，这里因为用了额外的变量b，所以空间复杂度为O(1)
//            // time::O(sqrt(c/2))-->O(sqrt(c));//因为时间复杂度会忽略常数部分，因此时间复杂度为O(sqrt(c))
//            //因为a2+b2=c  --->b2=c-a2  ----> b=✓c-✓a2;也就是b=sqrt(c-pow(a,2));
//            int b =(int)sqrt(c - a * a);//又因为sqrt是一个double的值，因此我们要将它强转为int
//            if (a * a + b * b == c)
//                return true;
//        }
//        return false;
//    }
//};

//class Solution {
//public:
//    bool judgeSquareSum(int c) {
//        int a = 0, b = (int)sqrt(c);
//        while (a <= b) {
//            //避免整数溢位问题
//            if (a * a == c - b * b) {
//                return true;
//            }
//            else if (a * a < c - b * b) {
//                ++a;
//            }
//            else {
//                --b;
//            }
//        }
//        return false;
//    }
//};
//

